package com.wang.leetcode;

import java.util.LinkedList;

/**
 * @Author: along
 * @Create: 2021/4/14 11:04
 * @Description:用两个栈来实现队列
 */

/*原因的话是Stack继承了Vector接口,而Vector底层是一个Object[]数组,那么就要考虑空间扩容和移位的问题了。
可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。*/
public class Sword09 {
    class CQueue {
        //这里使用的是LinkeList来做容器比Stack效率提高40%
        LinkedList<Integer> stack1;
        LinkedList<Integer> stack2;
        public CQueue() {
            stack1 = new LinkedList<Integer>();
            stack2 = new LinkedList<Integer>();
        }

        public void appendTail(int value) {
            stack1.add(value);
        }

        public int deleteHead() {
            if(stack2.isEmpty()) {
                if(stack1.isEmpty()) return -1;
                while(!stack1.isEmpty()){
                    stack2.add(stack1.pop());
                }
                return stack2.pop();
            }
            else{
                return stack2.pop();
            }
        }
    }
}
